683. Частичная сумма матрицы

Задана матрица чисел a_ij, где 1 ≤ i ≤ n, 1 ≤ j ≤ m. Для всех i, j вычислите частичные суммы

Вход. Первая строка содержит размеры матрицы n и m (1 ≤ n, m ≤ 1000). Далее следует описание самой матрицы a_ij (1 ≤ a_ij ≤ 1000): каждая из следующих n строк содержит по m чисел.

Выход. Выведите матрицу частичных сумм S_ij: n строк по m чисел.

Пример входа	Пример выхода
3 5 1 2 3 4 5 5 4 3 2 1 2 3 1 5 4	1 3 6 10 15 6 12 18 24 30 8 17 24 35 45

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть а – входной массив, s – массив частичных сумм. Будем заполнять массив s по строкам в порядке возрастания, а ячейки внутри каждой строки – по возрастанию столбцов. Предположим, что на данный момент все значения массива s уже вычислены вплоть до s[i][j].

Тогда

s[i][j] = s[i – 1][j] + s[i][j – 1] – s[i – 1][j – 1] + a_ij

Пример

Рассмотрим для заданного примера как вычислить значение s[3][5].

s[3][5] = s[2][5] + s[3][4] – s[2][4] + a₃₅ = 30 + 35 – 24 + 4 = 45

Упражнение

Для заданного массива a_ij вычислите значения элементов массива s_ij.

Реализация алгоритма

Объявим два двумерных массива.

#define MAX 1001

int a[MAX][MAX], s[MAX][MAX];

Читаем входные данные.

scanf("%d %d",&n,&m);

for(i = 1; i <= n; i++)

for(j = 1; j <= m; j++)

scanf("%d",&a[i][j]);

Вычисляем частичные суммы.

memset(s,0,sizeof(s));

for(i = 1; i <= n; i++)

for(j = 1; j <= m; j++)

s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];

Выводим результирующий массив частичных сумм.

for(i = 1; i <= n; i++)

{

for(j = 1; j <= m; j++)

printf("%d ",s[i][j]);

printf("\n");

}

Реализация алгоритма на лету

Читаем очередное значение a_ij и на лету пересчитываем и выводим частичную сумму S_ij. В таком случае входной массив содержать не надо.

#include <stdio.h>

#include <string.h>

#define MAX 1001

int i, j, n, m, value;

int mas[MAX][MAX];

int main(void)

{

scanf("%d %d",&n,&m);

memset(mas,0,sizeof(mas));

for(i = 1; i <= n; i++)

{

for(j = 1; j <= m; j++)

{

scanf("%d",&value);

mas[i][j] = mas[i][j-1] + mas[i-1][j] - mas[i-1][j-1] + value;

printf("%d ",mas[i][j]);

}

printf("\n");

}

return 0;

}